// Created by wxx on 2021/10/26 10:24
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {

        if (matrix.empty() || matrix[0].empty()) return 0;
        int n = matrix.size(), m = matrix[0].size();

        vector<vector<int>> h(n, vector<int>(m, 0));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (matrix[i][j] == '1') {
                    if (i) h[i][j] = h[i - 1][j] + 1;
                    else h[i][j] = 1;
                }

        int res = 0;
        for (int i = 0; i < n; i++) res = max(res, find(h[i]));

        return res;
    }

    int find(vector<int>& h) {

        int n = h.size();

        stack<int> stk;
        int l[n], r[n];

        for (int i = 0; i < n; i++) {
            while (stk.size() && h[stk.top()] >= h[i]) stk.pop();
            if (stk.empty()) l[i] = -1;
            else l[i] = stk.top();
            stk.push(i);
        }

        stk = stack<int>();  // 清空栈，不存在clear()
        for (int i = n - 1; i >= 0; i--) {
            while (stk.size() && h[stk.top()] >= h[i]) stk.pop();
            if (stk.empty()) r[i] = n;
            else r[i] = stk.top();
            stk.push(i);
        }

        int res = 0;
        for (int i = 0; i < n; i++) res = max(res, h[i] * (r[i] - l[i] - 1));
        return res;
    }
};

int main() {

    vector<vector<char>> matrix = {
            {'1', '0', '1', '0', '0'},
            {'1', '0', '1', '1', '1'},
            {'1', '1', '1', '1', '1'},
            {'1', '0', '0', '1', '0'}
    };
    cout << Solution().maximalRectangle(matrix) << endl;  // 6

    return 0;
}
